// Copyright 2010, Vanya Davidenko.
// Используемая кодировка: UTF-8.

#ifndef SCRW_SET_RECOGNIZER_H_
#define SCRW_SET_RECOGNIZER_H_

#include <assert.h>
#include <deque>
#include <set>
#include <string>
#include <vector>

#include <libv/check.h>


namespace scrw
{

/** Класс компилирует множество ASCII-строк в детерменированный конечный автомат
  * и за линейное определяет принадлежность некоторой строки этому множеству.
  * Поддерживается 2 режима: учитывающий регистр букв и игнорирующий его. */
class SetRecognizer
{
  public:
    typedef ::std::string Word;
    typedef ::std::set<Word> WordsSet;
    typedef int StateID;

    SetRecognizer()
        : char_mapping_table_(size_t(NUM_ASCII_CHARS), INVALID_CHAR_ID)
    {
        InitDfa();
    }

    SetRecognizer(const WordsSet& words, bool case_sensitive)
        : char_mapping_table_(size_t(NUM_ASCII_CHARS), INVALID_CHAR_ID)
    {
        BuildCharTable(words, case_sensitive);

        InitDfa();
        BuildDfa(words);
    }


    bool Check(const Word& word) const
    {
        return Check(word.data(), word.size());
    }


    template<typename TAsciiChar>
    bool Check(const TAsciiChar* word, const ::std::ptrdiff_t word_size) const
    {
        return IsFinal(Process(word, word_size));
    }


    template<typename TAsciiChar>
    StateID Process(const TAsciiChar* word,
                    const ::std::ptrdiff_t word_size) const
    {
        PRECOND(word != NULL);
        PRECOND(word_size >= 0);

        if ( word_size == 0 )
            return 0;

        StateID state_id = 0;
        for ( const TAsciiChar* i = word ; i - word != word_size ; ++i )
        {
            if ( char_id(*i) == INVALID_CHAR_ID ||
                 dfa_[state_id][char_id(*i)] == INVALID_STATE_ID )
                return INVALID_STATE_ID;

            state_id = dfa_[state_id][char_id(*i)];
        }
        return state_id;
    }


    bool IsFinal(const StateID state_id) const
    {
        PRECOND(state_id < static_cast<StateID>(final_states_.size()));

        if ( state_id == INVALID_STATE_ID )
            return false;

        return final_states_[state_id];
    }


    size_t num_state_ids() const
    {
        return dfa_.size();
    }



  private:
    typedef int CharID;
    typedef ::std::vector<StateID> State;
    typedef ::std::deque<State> Dfa;

    enum { NUM_ASCII_CHARS = 128, INVALID_STATE_ID = -1, INVALID_CHAR_ID = -1 };


    char LetterInAnotherCase(const char c) const
    {
        if ( 'a' <= c && c <= 'z' )
            return c - 'a' + 'A';
        else if ( 'A' <= c && c <= 'Z' )
            return c - 'A' + 'a';

        return c;
    }


    char LetterInLowerCase(const char c) const
    {
        if ( 'A' <= c && c <= 'Z' )
            return c - 'A' + 'a';

        return c;
    }


    ::std::deque<bool> UsedCharacters(const WordsSet& words) const
    {
        ::std::deque<bool> used_chars(NUM_ASCII_CHARS, false);

        for ( WordsSet::const_iterator \
              i = words.begin() ; i != words.end() ; ++i )
        {
            for ( Word::const_iterator j = i->begin() ; j != i->end() ; ++j )
            {
                assert(0 <= *j && *j < NUM_ASCII_CHARS);
                used_chars[*j] = true;
            }
        }

        return used_chars;
    }


    void BuildCharTable(const WordsSet& words, const bool case_sensitive)
    {
        ::std::deque<bool> used_chars = UsedCharacters(words);

        for ( size_t i = 0 ; i != used_chars.size() ; ++i )
        {
            if ( used_chars[i] )
            {
                const int index = static_cast<int>(chars_.size());
                if ( case_sensitive )
                {
                    chars_.push_back(static_cast<char>(i));
                    char_mapping_table_[i] = index;
                }
                else
                {
                    const char c = LetterInAnotherCase(static_cast<char>(i));
                    if ( char_mapping_table_[c] == INVALID_CHAR_ID )
                    {
                        chars_.push_back(LetterInLowerCase(c));
                        char_mapping_table_[i] = index;
                        char_mapping_table_[c] = index;
                    }
                }
            }
        }
    }


    template<typename TAsciiChar>
    CharID char_id(const TAsciiChar c) const
    {
        if ( c < 0 || c >= NUM_ASCII_CHARS )
            return INVALID_CHAR_ID;

        return char_mapping_table_[c];
    }


    StateID NewState()
    {
        State state;
        state.reserve(chars_.size());
        state.resize(chars_.size(), INVALID_STATE_ID);

        dfa_.push_back(state);
        return static_cast<StateID>(dfa_.size() - 1);
    }


    void MakeStateFinal(const StateID state_id)
    {
        assert(final_states_.size() <= dfa_.size());
        final_states_.resize(dfa_.size(), false);
        final_states_[state_id] = true;
    }


    void InitDfa()
    {
        assert(dfa_.empty());
        NewState();
        final_states_.resize(1, false);
    }


    void BuildDfa(const WordsSet& words)
    {
        assert(dfa_.empty() == false);
        for ( WordsSet::const_iterator \
              i = words.begin() ; i != words.end() ; ++i )
            AddWordToDfa(*i);
    }


    void AddWordToDfa(const Word& word)
    {
        StateID state_id = 0;
        for ( Word::const_iterator i = word.begin() ; i != word.end() ; ++i )
        {
            if ( dfa_[state_id][char_id(*i)] == INVALID_STATE_ID )
                dfa_[state_id][char_id(*i)] = NewState();

            state_id = dfa_[state_id][char_id(*i)];
        }

        MakeStateFinal(state_id);
    }



    ::std::deque<int> char_mapping_table_;  // char -> CharID
    ::std::deque<char> chars_;  // CharID -> char

    Dfa dfa_;
    ::std::deque<bool> final_states_;
};

}  // scrw

#endif  // SCRW_SET_RECOGNIZER_H_
